package codingforgreat.class45;

import java.util.HashSet;

public class Problem_0291_WordPatternII {
    public static boolean wordPatternMatch(String pattern, String str) {
        return match(str, pattern, 0, 0, new String[26], new HashSet<>());
    }

    // 题目有限制，str和pattern其中的字符，一定是a~z小写
    // p[a] -> "abc"
    // p[b] -> "fbf"
    // 需要指代的表最多26长度
    // String[] map -> new String[26]
    // p[a] -> "abc"   map[0] -> "abc"
    // p[b] -> "fbf"   map[1] -> "fbf";
    // p[z] -> "kfk"   map[25] -> "kfk"
    // HashSet<String> set -> map中指代了哪些字符串
    // str[si.......]  是不是符合  p[pi......]？符合返回true，不符合返回false
    // 之前的决定！由map和set，告诉我！不能冲突！
    public static boolean match(String s, String p, int si, int pi, String[] map, HashSet<String> set) {
        if (pi == p.length() && si == s.length()) {
            return true;
        }
        // str和pattern，并没有都结束！
        if (pi == p.length() || si == s.length()) {
            return false;
        }
        //  str和pattern，都没结束！

        char ch = p.charAt(pi);
        String cur = map[ch - 'a'];
        if (cur != null) { // 当前p[pi]已经指定过了！
            return si + cur.length() <= s.length() // 不能越界！
                    && cur.equals(s.substring(si, si + cur.length()))
                    && match(s, p, si + cur.length(), pi + 1, map, set);
        }
        // p[pi]没指定！
        int end = s.length();
        // 剪枝！重要的剪枝！
        for (int i = p.length() - 1; i > pi; i--) {
            end -= map[p.charAt(i) - 'a'] == null ? 1 : map[p.charAt(i) - 'a'].length();
        }
        for (int i = si; i < end; i++) {
            //  从si出发的所有前缀串，全试
            cur = s.substring(si, i + 1);
            // 但是，只有这个前缀串，之前没占过别的坑！才能去尝试
            if (!set.contains(cur)) {
                set.add(cur);
                map[ch - 'a'] = cur;
                if (match(s, p, i + 1, pi + 1, map, set)) {
                    return true;
                }
                map[ch - 'a'] = null;
                set.remove(cur);
            }
        }
        return false;
    }


    public static boolean WordPath(String words,String pattern){
        return match1(words,pattern,0,0,new String[26],new HashSet<>());
    }

    private static boolean match1(String words, String pattern, int si,int pi, String[] strings, HashSet<String> set) {
        if(si == words.length() && pi == pattern.length()){
            return  true;
        }
        if(si == words.length() || pi == pattern.length()){
            return false;
        }
        char ch = pattern.charAt(pi);
        String cur = strings[ch - 'a'];
        if(cur != null){
            return si + cur.length() <= words.length() // 不能越界！
                    && cur.equals(words.substring(si, si + cur.length()))
                    && match(words, pattern, si + cur.length(), pi + 1, strings, set);
        }
        int end = words.length();
        for(int i = pattern.length() - 1;i > pi;i--){
            end -= strings[pattern.charAt(i) - 'a'] != null ? strings[pattern.charAt(i) - 'a'].length() : 1 ;
        }
        for(int i = si;i < end;i++){
            cur = words.substring(i,i + 1);
            if(set.contains(cur)){
                continue;
            }
            strings[ch- 'a'] = cur;
            set.add(cur);
            if (match(words, pattern, i + 1, pi + 1, strings, set)) {
                return true;
            }
            strings[ch - 'a'] = null;
            set.remove(cur);
        }
        return false;
    }
    public static String[] getwordsAndpattern(){
        int wordsSize = (int) (Math.random() * (100)) + 1;
        int patternSize = wordsSize + (int) (Math.random() * (50)) + 1;
        char[] w = new char[wordsSize];
        for (int i = 0; i < w.length; i++) {
            w[i] = (char) ((Math.random() * (26)) + 'a');
        }
        char[] p = new char[patternSize];
        for (int i = 0; i < p.length; i++) {
            p[i] = (char) ((Math.random() * (26)) + 'a');
        }
        return new String[]{new String(w), new String(p)};
    }

    public static void main(String[] args) {
        boolean t = true;
        for (int i = 0; i < 100; i++) {
            String[] wp = getwordsAndpattern();
            String words  = wp[0];
            String pattern = wp[1];
            boolean ans1 = wordPatternMatch(pattern,words);
            boolean ans2 = WordPath(words,pattern);
            if(ans1 != ans2){
                t = false;
                System.out.println("OOPS!!!!");
            }
        }
        if(t){
            System.out.println("NICE!!!!");
        }
    }
}
